package lis;

/**
 *
 * @author Selcuk Orhan DEMIREL <orhandemirel@msn.com>
 */
public class Liseq {

    int [] seqCount;

    public int[] findLiseq(int[] arr)
    {
        seqCount = new int[arr.length];
        int n;
        int max = 0;
        int ind = 0;

        for(int i=0;i< arr.length;i++)
        {
            n = liseqNum(i, arr);
            if(n > max)
            {
                max = n;
                ind = i;
            }
        }
        return new int[]{max,ind} ;
    }
    
    public int liseqNum(int i, int []  arr)
    {
        if(i == arr.length)
            return 0;

        if(seqCount[i] == 0)
        {
            int j = i + 1;
            while(j < arr.length && arr[j] < arr[i])
                j++;

            int num = 1 + liseqNum( j, arr);

            seqCount[i] = num;
            
            return num;
        }
        else return seqCount[i]; // Memoization
    }
}
